#include<stdio.h>
#define Len 8

int a[Len] = {5, 2, 4, 7, 1, 3, 2, 6};


int partition(int start, int end)
{
  int pivot = a[start];
  int small[Len];
  int big[Len];
  
  int i, j = 0, k = 0;
  for (i = start; i <= end; ++i){
    if (a[i] < pivot){
      small[j++] = a[i];
    }
    else{
      big[k++] = a[i];
    }
  }

  int mid = start + j;

  int n = 0;
  for (i = start; i < start + j; ++i){
    a[i] = small[n++];
  }

  a[i] = pivot;
  int m = 0;

  for (i = start + j; i < start + j + k; ++i){
    a[i] = big[m++];
  }

  return mid;
}

int order_statistic(int start, int end, int k)
{
  int i = partition(start, end) - start + 1; /*返回的i是第i + 1小，即i = 0时对于第一小，也就是最小, 另外这里的i应该相对于start来确定其是第几小*/


  if (k == i){
    return a[i + start - 1];
  }
  else if (k > i ){
    order_statistic(i + start, end, k - i);
  }
  else{
    order_statistic(start, i + start - 1, k);
  }
}

int main()
{
  printf("%d\n", order_statistic(0, 7, 8));  
}
